package leetcode_周赛._2023._10;

/**
 * 第 365 场周赛 <p>
 * AC_2
 *
 * @author yezh
 * @date 2023/10/7 10:31
 */
public class _01 {

    /**
     * 2875.无限数组的最短子数组 <br />
     * 算法: 滑动窗口 <br />
     * 一个 target 中最多包含 target / sum(nums) 个完整数组 <br />
     * target % sum(nums) 所需的元素从两个完整数组中取, 所需元素的数量肯定 < n
     */
    public static int minSizeSubarray(int[] nums, int target) {
        int ans = Integer.MAX_VALUE, n = nums.length, sum = 0;
        for (int num : nums) sum += num;
        int res = target % sum;
        for (int left = 0, right = 0, cur = 0; right < 2 * n; ++right) {
            cur += nums[right % n];
            while (cur > res) {
                cur -= nums[left % n];
                ++left;
            }
            if (cur == res) ans = Math.min(ans, right - left + 1);
        }
        return ans == Integer.MAX_VALUE ? -1 : ans + target / sum * n;
    }

}
